Historically, society has relied upon paper bound mechanisms to verify the integrity of documents and to authenticate the identity of originators of these documents and the information contained therein. Sometimes, perhaps when a dispute arose, the validity of such documents would be contested. As a result, society has developed and evolved various accepted procedures and mechanisms to contest the veracity of such documents, as well as procedures and mechanisms by which the accuracy and integrity of such documents can be established and maintained. For example, the State of California has promulgated Probate Code sections to establish such procedures and mechanisms for the designation and declaration of Durable Power of Attorney and ‘Attorneys-in-Fact’. In many instances, Public Notaries are required to help establish the identity of the signatory to a document, for example a Deed of Trust. In other instances the law may recognize the usefulness of expert handwriting analysis to determine the veracity of a signature, perhaps the signature of a testator on a contested Last Will and Testament.
With the evolution of modern technology, the use of electronic documents has become increasingly widespread. Such electronic documents can include digital representations of readable text, as well as digital representations of video and audio data, laboratory and research records, as well as auditing and forensic evidence used in establishing the validity and authenticity of these various information types.
Digital records may be created in a variety of ways. For example, a document may be created or modified on a digital computer and saved as a digital file. Computers or other systems may also create binary data and programs, and can modify and append to existing data and programs. A printed document may be scanned and the scanner output saved as a digital file. A digital camera can capture video and/or audio information from a scene, and directly save the captured information as a digital file. In a variety of ways, pre-existing documents, text, images, graphics, murals, videotape, soundtracks, photographic film and the like can also be captured and saved as a digital file. Thus, as used herein, “document” shall be understood to include without limitation information that can be stored or represented in any type of digital format, including the aggregation of multiple documents of differing types, regardless of whether any type of intermediate storage may be used. The terms “digital file” (DF) or “digital encoded record” (DER) shall be understood to include without limitation such digital format representation of one or more such documents.
It is often important to be able to authenticate that a document has not been altered after its creation. For example, merely changing the day of the month upon which a contract appears to have been signed may create advantage for one party to the contract. A digital recording of an interview may be altered, perhaps almost undetectable, to delete an embarrassingly long pause between a question and an answer. A digital photograph may be altered to change the image ostensibly captured by the camera. Equally seriously, digital files may be maliciously altered, for example to create so-called computer viruses that can damage other files on a user's computer system.
Modern technology permits information to be revised all too easily. The lamentable fact that such revisions can often be made without telltale signs of tampering means that there is often insufficient credible evidence attesting to the authenticity and accuracy of such documents or records, including digital documents or records.
How then to authenticate that such documents have not been altered. In the case of printed materials, contracts, photographs, and the like, duplicate copies may be made contemporaneously with the creation of the original document. But such procedure offers little protection against someone, for example the original author, altering and recopying the original document, and substituting newly made copies of the altered document for the original document. So doing could permit repudiating authorship of the original document in favor of the altered document. To some extent this situation may be partially guarded against by promptly distributing the original copies of the true document to at least one trustworthy individual, an escrow holder perhaps. Distributing the document to a collection of trustworthy recipients provides some relief against the possibility that the document may become irretrievable from a single individual. However, the level of confidence provided by such entrustment to escrow holders can diminish as a function of time. The trusted individuals may move away or die, or the documents entrusted to them may become misplaced, lost, damaged, deteriorated with age, stolen, or otherwise irretrievable. It is also possible that one or more such individuals might be bribed or otherwise compromised to allow others to gain access to the information in escrow.
But if the entrusted document contains confidential information, distribution even to trusted individuals introduces the risk that the document may later be disclosed in an unauthorized fashion to a third party. Such risk increases with the number of individuals with whom the document is entrusted. In general, a system seeking to protect authenticity of a document through distribution of its contents risks unauthorized disclosure of confidential information in or associated with the document.
One-way cryptographic hash functions have been proposed as tools useful in assessing the integrity of digitally stored information through the use of message digests. A one-way hash function, which may also be known as a cryptographic fingerprint, cryptographic checksum, or message digest function, preferably has the property that it is collision-resistant or collision-free: that is it difficult to find or to construct two different input values, sometimes called the pre-image, that when passed through the same one-way hash function produce identical output values, sometimes called the hash value. Several one-way hash functions with well-understood collision-resistant properties are in the public domain, many of which functions have well known and unimputable reputations. Exemplary one-way hash functions include the proposed secure hash standards SHA-256, SHA-384, and SHA-512, or the Federal Information Processing Standard (FIPS) Secure Hash Algorithm (SHA-1, FIPS 180-1), both published by the United States National Institute of Standards and Technology (NIST), Message Digest 5 (MD5) developed by Ron Rivest, SNEFRU developed by Ralph Merkle, OpenBSD bcrypt proposed by Niels Provos and David Mazières. Advantageously there is a body of established social, commercial, and legal precedent associated with the use of many prior-art one-way hash functions, often dealing with PKI and digital signature applications.
One exemplary commercial endeavor that uses one-way hash functions includes Tripwire, commercialized by Tripwire, Inc. of Portland, Oreg., which seeks to provide an effective mechanism to monitor integrity of digital files. U.S. Pat. No. 5,530,757 to Krawczyk (1996) discloses systems that purport to distribute the results of one-way cryptographic hash functions to a plurality of storage locations. However Krawczyk appears to promulgate different hashed values to different storage locations without regard to the attendant inefficiencies resulting from such a convoluted distribution scheme. Further, Krawcyzk's approach presupposes that a majority of all such storage locations will always be available for verification to occur. In practice, the operational requirements of a Krawczyk-type system would create undesirable complexity during the system encoding and verification phases.
Various solutions have been proposed in the prior art to verify the integrity of electronic documents and specifically to affix electronic signatures to such documents. But such prior-art solutions based upon cryptographic hash functions still lack sufficient capability and control to implement practical use of electronic signatures, especially under applicable regulations and statutes. Indeed the impracticality of such approaches is demonstrated by their lack of widespread commercial adoption.
Other prior art approaches rely upon encryption and cryptography to provide so-called digital signatures in an attempt to authenticate identity of a document originator and provide some assurance as to integrity of the electronic document itself. However such approaches are justly criticized for their complexity, the frequent unpredictability of their behavior, uncertainty as to the effectiveness of any security that is imparted, as well as the fragility of the overall systems.
Several techniques are commonly known to encrypt digital files, including files that may represent documents. Such techniques seek to minimize the risks associated with disclosure by encrypting documents that contain confidential information. In so-called symmetric (or secret key) encryption, a digital file is encrypted with a key, and then transmitted to a recipient who then decrypts or deciphers the digital file using the same key. But it is not practical to share the same secret key securely with a number of potential recipients, especially on a global scale. If anyone in possession of the secret key permits it to be comprised (intentionally or otherwise), any information encrypted with that key may also be compromised. Further, the secret keys must somehow be communicated to all intended recipients, but not to others, in a secure fashion. Managing distribution of these secret keys to a large number of recipients, and ensuring that the keys remain secret over any length of time, can be a difficult and intractable problem.
So-called asymmetric (or public key) encryption uses pairs of mathematically linked keys such that a document encrypted with one of the keys (a “public key”) can only be decrypted using the counterpart key (a “private key”). In this prior art encryption technique, the recipient's public key is obtained and is used to encrypt a digital file. The thus encrypted digital file is then transmitted to the recipient, and can only be decrypted with knowledge of the corresponding private key. Such public key cryptography overcomes the need to share secret keys with other parties. However, these prior art techniques rely upon some method of distributing the relevant public keys to other parties and require all parties to maintain absolute confidentiality of their private keys.
Thus, symmetric and asymmetric cryptography each rely upon maintaining the absolute confidentiality of the secret or private key. Unfortunately there are numerous ways by which these keys can become compromised, a problem that is exacerbated when the keys are frequently reused. Public key cryptography further requires an extremely reliable mechanism to ensure than an individual's private key has not been surreptitiously compromised. If an individual private key became known to an unauthorized person, or a copy of an individual private key were obtained by an otherwise authorized third-party, it would be nearly impossible to distinguish between authorized and unauthorized users of the cryptographic keys. Thus, the protection provided by modern cryptography is only as good as the ability to ensure that relevant keys are accessible only to authorized individuals, to the exclusion of all others.
Mitigating risks associated with use of such keys often requires implementing access control procedures that allow properly authenticated individuals access to these keys, while denying access to unauthorized parties. Such prior art access controls include use of passwords, biometrics, and access tokens, although the high cost and complexity of biometrics and tokens limit their widespread use. As a result, passwords remain the most prevalent access control mechanism deployed today.
Private keys are typically stored and thus may be vulnerable to compromise from other parties. The level of protection afforded to key storage is typically no better than one's ability to select and guard passwords that cannot easily be compromised, e.g., by guessing or theft. Unfortunately, many easily implemented techniques known in the art enable an unauthorized party to circumvent protection afforded by passwords, and thus improperly gain direct assess to the underlying private keys. As computer processing power continues to increase exponentially, it is becoming increasingly possible to utilize well understood cryptographic attacks to circumvent such protections. Consequently, absent costly and complicated devices (e.g., biometrics, tokens, etc.), the overall security afforded to these private keys can be no greater than the security afforded by the passwords protecting these keys.
Thus, absent adequate legal and technical assurance that a private key remains in the control and custody of the sender or originator of a message, it is possible for the sender to later deny having processed the information. Stated differently, absent such safeguards, the possibility exists that a person can later disavow the use of his or her electronic signature, for example as affixed to a contract or other document.
Prior art techniques that rely upon use of public key cryptography also require absolute knowledge that a given public key was issued by a particular individual and by no other. Understandably, authentication and confidentiality of any document could be completely undermined and compromised if unauthorized public keys could be created and distributed. If one could generate a counterfeit key pair and then substitute the counterfeit public key for a genuine public key, it would be possible using the counterfeit private key to decrypt information encrypted using the now-substituted counterfeit public key. Sharing an individual's public keys with a large number of potential recipients, especially on a global scale, is a difficult undertaking. It is known in the art to use a central authority to facilitate the widespread distribution of public keys in a secure fashion. However, a recipient must have a nearly blind level of trust in one or more of these distribution hierarchies, each of which culminates in a central facility that somehow ensures that a given public key is properly associated with a given individual. But should the integrity of the central facility be compromised in any way, the entire premise enabling document authentication can suddenly become untenable.
As used herein, the term “public key infrastructure” (PKI) is understood to include the collection of hardware, software, polices, and individuals that, when fully and properly implemented, can provide a suite of information security assurances, including varying levels of confidentiality, data integrity, and authentication. However, formidable challenges remain that impede widespread use of PKI, including access controls on private keys, poor interoperability, limited operational experience, high implementation costs, lack of well-defined and enforced security polices, and insufficiently trained personnel. As a result, although PKI technology has been available for many years, most adopters of this technology remain at an early stage of implementation, and it is still not well understood how well this technology will truly scale and interoperate within the business and government sectors. For example, the United States General Accounting Office has stated (GAO-01-277, 2/2001) that PKI still faces formidable challenges and that to date most PKI deployments seem to be limited to pilot programs, targeted special-purpose applications, or the like. In the face of such just criticism, as well as problems associated with interoperability, many issues must be overcome before PKI-type technology will be widely and effectively adopted.
By way of example, companies such as Verisign, Inc. of Mountain View, Calif. will provide an assertion that a given public key indeed belongs to a given entity, and will distribute such assertion in the form of a so-called digital certificate that can be used to encrypt documents and affix digital signatures to such documents. Thus if a user has sufficient trust in these assertions, there would be a reasonable belief that the public key belongs to the individual so endorsed by Verisign, Inc. But such prior art techniques require that a user have almost blind trust in the integrity of such companies, as well as have absolute confidence in the companies' ability to maintain these assertions over time. Without absolutely reliable means to ensure an individual's private key has not been compromised, intentionally or otherwise, an individual could reasonably claim that their key had been used in an unauthorized fashion, thus undermining the effectiveness of PKI-based systems.
But even if relevant cryptographic keys could remain forever sacrosanct, the author of an original undistributed document could still subsequently alter and then re-encrypt or re-sign the document, permitting successful modification of the original document. As such, prior art methods using public and secret key cryptography are insufficient to authenticate that a document has not been altered, even by its author, after its creation. Simply stated, it has been quite difficult in the prior art to reliably prevent repudiation with any real degree of assurance.
Further, the algorithms used in public and private key cryptography tend to be very computationally intensive, often requiring powerful hardware that might not otherwise be needed. The result is to increase the commercial cost of such protection as may be provided by such techniques. Yet another disadvantage of encryption techniques is that they often are subject to export and import restrictions imposed by various governments, including the U.S. government. The degree of difficulty in obtaining the appropriate import and export licenses for products that employ the use of encryption hardware and/or software can greatly hamper the commercial viability of such products.
In summary, significant and widespread barriers continue to preclude the general adoption of the above-described prior-art solutions, whether based on public key cryptography or upon traditional cryptographic techniques. It is fair to say that information systems that depend upon maintaining secret information, such as cryptographic keys, are only as trustworthy as the least trusted component within the overall system, analogous to the weakest link in a chain. This statement holds true whether the system is composed of individuals, of organizations, or an amalgamation of electronic or other computer storage and retrieval devices. Consequently, cryptographic techniques that are built solely upon the foundation of closely guarded secrets must not be relied upon to preserve confidentiality or authenticity of documents. Due to limitations inherent in prior-art methodologies, society still relies heavily upon paper bound protocols and processes, even though high speed computers and communications media such as the Internet have come into widespread use.
Thus, there is a need for a simple and reliable system and protocol to assess the integrity of large quantities of digitally stored information, and to determine at some later date whether any monitored information records have been altered. Such protective functionality should preferably include a mechanism to apply electronic signatures to electronic records, to permit verification of integrity and validity of these records to which such signatures have been applied, and to determine whether such records and associated signatures have been altered. Preferably such verification and authentication protective functionality should be associated directly with the document or with a document characteristic not readily altered or counterfeited. These capabilities should not require the use of public or private key cryptography, and should operate without having to entrust confidential information to any central entity or organization. Furthermore, such system and protocol should function without a need to maintain secrets that could be lost, stolen, or otherwise compromised. Further still, the nature of the protection provided by such system and protocol should be such that a disclosure, authorized or otherwise, of information maintained within the system will not jeopardize confidential or functional properties of the system. Such system should operate to prevent repudiation in the event of the theft or re-signing of a document, and the protection afforded should not diminish with time.
Further, there is a need to implement such protection using a distributed information system and protocol whereby characteristic(s) of the original document are distributed to a sufficient number of partially trusted recipients, none of whom requires any knowledge as to the nature or contents of the original document, or its author, thus protecting confidentiality. Preferably, the protection afforded by such system and protocol should be built upon accumulated incremental trust imparted by a collection (or cluster) of such partially trusted entities, such that any loss of confidence in one or even several entities entity will not appreciably diminish overall system protection. Further, the loss or unavailability of one or more distributed entities should not reduce trustworthiness of the overall system by more than the incremental level of trust provided by the unavailable entities. Further, each of these partially trusted entities should be able to independently verify and attest to the time that the document, or an attribute of the document, was registered by such a system and protocol, thus eliminating the need for a single trusted time-stamping authority.
In short, there is a need for a system and protocol by which authenticity and integrity of a document representable as a digital file may be ascertained at some later date, without knowledge of the original document. There is a need for a system and protocol meeting the above goals that also complies with relevant regulatory and statutory requirements, so as to be legally enforceable, and can also be implemented with existing hardware and software tools. The resultant system and protocol should also permit electronic signatures to be substituted for original handwritten signatures on documents, agreements, and contracts that previously required paper bound processes and methods to retain the validity, enforceability and full legal effect otherwise accorded to original handwritten signatures. Further, such system and protocol should permit capturing and promulgating the intent underlying prospective use of the electronic signature. In addition, an anonymous user of the system and protocol should be enabled to later establish his or her identity as an author or signer of a document promulgated by the system. Preferably such system should usable with a range of computing systems including cellular telephones, PDAs, automated teller machines, among other information type appliances.
The present invention provides such a distributed information system and protocol.